#define  _CRT_SECURE_NO_WARNINGS 1


https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/submissions/644682455/
class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for (char& c : s)
        {
            if (ret.size() && ret.back() == c)
                ret.pop_back();
            else
                ret += c;
        }
        return ret;
    }
};

https://leetcode.cn/problems/backspace-string-compare/submissions/644683592/
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string value1, value2;
        for (char& c : s)
        {
            if (value1.size() && c == '#')
                value1.pop_back();
            else
                if (c != '#')
                    value1 += c;

        }
        for (char& c : t)
        {
            if (value2.size() && c == '#')
                value2.pop_back();
            else
                if (c != '#')
                    value2 += c;
        }
        return value1 == value2;
    }
};


https://leetcode.cn/problems/basic-calculator-ii/submissions/644906721/
class Solution {
public:
    int calculate(string s) {
        vector<int> st;
        int i = 0, n = s.size();
        int op = '+';
        while (i < n)
        {
            if (s[i] == ' ')
                i++;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                if (op == '+') st.push_back(tmp);
                else if (op == '-') st.push_back(-tmp);
                else if (op == '*') st.back() *= tmp;
                else st.back() /= tmp;
            }
            else
                op = s[i++];
        }
        int ret = 0;
        for (auto num : st)
            ret += num;

        return ret;
    }
};

https://leetcode.cn/problems/decode-string/submissions/644912931/
class Solution {
public:
    string decodeString(string s) {
        stack<int> st1;
        stack<string> st2;
        st2.push("");
        int i = 0, n = s.size();
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + s[i++] - '0';
                st1.push(tmp);
            }
            else if (s[i] == '[')
            {
                i++;
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                    tmp += s[i++];
                st2.push(tmp);
            }
            else if (s[i] == ']')
            {
                i++;
                int num = st1.top();
                st1.pop();
                string str = st2.top();
                st2.pop();
                string tmp;
                while (num--)
                    tmp += str;
                st2.top() += tmp;
            }
            else
            {
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                    tmp += s[i++];
                st2.top() += tmp;
            }
        }
        return st2.top();
    }
};

https://leetcode.cn/problems/validate-stack-sequences/submissions/644915963/
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int n1 = pushed.size(), n2 = popped.size();
        int cur1 = 0, cur2 = 0;
        stack<int> st;
        while (cur1 < n1)
        {
            if (st.empty())
                st.push(pushed[cur1++]);

            while (cur1 < n1 && st.top() != popped[cur2])
            {
                st.push(pushed[cur1++]);
            }
            while (cur2 < n2 && !st.empty() && st.top() == popped[cur2])
            {
                st.pop();
                cur2++;
            }
        }
        if (st.empty())
            return true;
        else
            return false;
    }
};